|
In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.〔. ("Complete set of logical connectives").〕〔. ("()unctional completeness of () set of logical operators").〕 A well-known complete set of connectives is , consisting of binary conjunction and negation. The singleton sets and are also functionally complete. In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.〔. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)〕 From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates. ==Formal definition== Given the Boolean domain B = , a set ''F'' of Boolean functions ''ƒ''i: B''ni'' → B is functionally complete if the clone on B generated by the basic functions ''ƒ''i contains all functions ''ƒ'': B''n'' → B, for all ''strictly positive'' integers . In other words, the set is functionally complete if every Boolean function that takes at least one variable can be expressed in terms of the functions ''ƒ''i. Since every Boolean function of at least one variable can be expressed in terms of binary Boolean functions, ''F'' is functionally complete if and only if every binary Boolean function can be expressed in terms of the functions in ''F''. A more natural condition would be that the clone generated by ''F'' consist of all functions ''ƒ'': B''n'' → B, for all integers . However, the examples given above are not functionally complete in this stronger sense because it is not possible to write a nullary function, i.e. a constant expression, in terms of ''F'' if ''F'' itself does not contain at least one nullary function. With this stronger definition, the smallest functionally complete sets would have 2 elements. Another natural condition would be that the clone generated by ''F'' together with the two nullary constant functions be functionally complete or, equivalently, functionally complete in the strong sense of the previous paragraph. The example of the Boolean function given by ''S''(''x'', ''y'', ''z'') = ''z'' if ''x'' = ''y'' and ''S''(''x'', ''y'', ''z'') = ''x'' otherwise shows that this condition is strictly weaker than functional completeness. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「functional completeness」の詳細全文を読む スポンサード リンク
|